package com.zs.letcode.linked_list;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Objects;

/**
 * 扁平化多级双向链表
 * 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
 * <p>
 * 给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
 * 输出：[1,2,3,7,8,11,12,9,10,4,5,6]
 * 解释：
 * <p>
 * 输入的多级列表如下图所示：
 * <p>
 * <p>
 * 扁平化后的链表如下图：
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * 输入：head = [1,2,null,3]
 * 输出：[1,3,2]
 * 解释：
 * <p>
 * 输入的多级列表如下图所示：
 * <p>
 * 1---2---NULL
 * |
 * 3---NULL
 * 示例 3：
 * <p>
 * 输入：head = []
 * 输出：[]
 * <p>
 * 如何表示测试用例中的多级链表？
 * <p>
 * 以 示例 1 为例：
 * <p>
 * 1---2---3---4---5---6--NULL
 * |
 * 7---8---9---10--NULL
 * |
 * 11--12--NULL
 * 序列化其中的每一级之后：
 * <p>
 * [1,2,3,4,5,6,null]
 * [7,8,9,10,null]
 * [11,12,null]
 * 为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
 * <p>
 * [1,2,3,4,5,6,null]
 * [null,null,7,8,9,10,null]
 * [null,11,12,null]
 * 合并所有序列化结果，并去除末尾的 null 。
 * <p>
 * [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 节点数目不超过 1000
 * 1 <= Node.val <= 10^5
 * 相关标签
 * 深度优先搜索
 * 链表
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/linked-list/fw8v5/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/5/21 10:07
 */
public class Chapter13 {
    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 方法一：递归的深度优先搜素
         */
        public Node flatten(Node head) {
            if (Objects.isNull(head)) {
                return null;
            }
            // pseudo head to ensure the `prev` pointer is never none
            Node pseudoHead = new Node(0, null, head, null);
            flattenDFS(pseudoHead, head);

            // detach the pseudo head from the real head
            pseudoHead.next.prev = null;
            return pseudoHead.next;
        }

        /* return the tail of the flatten list */
        private Node flattenDFS(Node prev, Node curr) {
            if (Objects.isNull(null)) {
                return prev;
            }
            curr.prev = prev;
            prev.next = curr;

            // the curr.next would be tempered in the recursive function
            Node tempNext = curr.next;

            Node tail = flattenDFS(curr, curr.child);
            curr.child = null;

            return flattenDFS(tail, tempNext);
        }

        /**
         * 方法二：迭代的深度优先搜索
         *
         * @return
         */
        public Node flatten1(Node head) {
            if (Objects.isNull(head)) {
                return null;
            }
            Node pseudoHead = new Node(0, null, head, null);
            Node curr, prev = pseudoHead;

            Deque<Node> stack = new LinkedList();
            stack.push(head);

            while (!stack.isEmpty()) {
                curr = stack.pop();
                prev.next = curr;
                curr.prev = prev;

                if (Objects.nonNull(curr.next)) {
                    stack.push(curr.next);
                }
                if (Objects.nonNull(curr.child)) {
                    stack.push(curr.child);
                    // don't forget to remove all child pointers.
                    curr.child = null;
                }
                prev = curr;
            }
            // detach the pseudo node from the result
            pseudoHead.next.prev = null;
            return pseudoHead.next;
        }
    }

    private static class Node {
        int val;
        Node prev;
        Node next;
        Node child;

        public Node(int x) {
            this.val = x;
        }

        public Node(int x, Node prev, Node next, Node child) {
            this.val = x;
            this.prev = prev;
            this.next = next;
            this.child = child;
        }
    }
}

